• Automation Software

Automation Software

• Command-Line Utilities

Command-Line Utilities

wrap lines to a maximum width of 80 in FILE

fold -w 80 -s FILE

• Hammerspoon

Hammerspoon

add stuff: open config, type in LaTeX, save, reload config

bind function to hotkey

hs.hotkey.bind({"functionKey", …}, "key",…, function()
  …
end)

functionKey: cmd alt ctrl
key: X \\ Left
the {} must stay even if it`s empty

show alert message

hs.alert.show("message")

generate system notification with title and content

hs.notify.new({title="title", informativeText="content"}):send()

define the current window as win

local win = hs.window.focusedWindow()

define win’s window frame as f

local f = win:frame()

position of f is (f.x, f.y) its width and height f.w, f.h

define the screen win at as screen

local screen = win:screen()

define screen's screen frame as max

local max = screen:frame()

update the frame of win as f

win:setFrame(f)

hs.pathwatcher.new(.....):start()

reload config

hs.reload()

automatically reload config

function reloadConfig(files)
    doReload = false
    for _,file in pairs(files) do
        if file:sub(-4) == ".lua" then
            doReload = true
        end
    end
    if doReload then
        hs.reload()
    end
end
myWatcher = hs.pathwatcher.new(os.getenv("HOME") .. "/.hammerspoon/", reloadConfig):start()
hs.alert.show("Config loaded")

get the home direction of the system

os.getenv("HOME")

connect string to path

..

call function whenever changes in direction

hs.pathwatcher.new("direction", function):start()

• Computer Science

Computer Science

• Discrete Mathematics for Computer Science
  • proof by induction

Discrete Mathematics for Computer Science

proof by induction

steps with example

• variable $n$
• property $P(n)$
• base case $P(0)$
• induction hypothesis
  • weak induction
    assume $P(n-1)$ is true
  • strong induction
    assume $P(k)$ is true $\forall k<n$
• induction step
  induction hypothesis $\Rightarrow P(n)$ is true

• Machine Learning
  • general problem format
  • machine learning is about building a function
    • simplification using feature vector
  • loss
    • zero-one loss
    • quadratic loss
  • empirical risk
  • three types of machine learning problems
    • classification problem
      • all possible training set
      • signature of machine learning function $\lambda$
      • classifier $h$ define a partition of $X$
    • regression problem
    • clustering problem
  • supervised/ unsupervised machine learning
• polynomial data fitting
  • interpolation in polynomial data fitting
• k-nearest neighbors predictor
  • Voronoi diagram
• gradient descent
  • stochastic gradient descent (SGD)
  • step size
  • subgradient
• logistic-regression classifier
  • score function for linear boundary
  • signed distance to hyperplane
  • logistic function
    • softmax function
  • cross entropy loss for binary classification
    • cross entropy loss for $K$-class case
• support vector machine (SVM)
  • binary support vector machine
    • separating hyperplane for binary support vector machine
    • hinge loss
      • empirical risk of binary support vector machine
  • soft linear support vector machine
    • subgradient of hinge function
  • support vector machine with kernel
    • representer theorem
    • support vector
    • kernel for support vector machine

Machine Learning

general problem format

given input $A$, want output $y\in Y$

$$f:A\to Y,y=f(a)\in Y\text{for }a\in A$$

• traditional approach
  hand-craft the function $f$
• machine learning
  build another function $\lambda$ and use it to generate an approximation $f$

machine learning is about building a function

• training data $L=\{(a_1,y_1),\cdots ,(a_n,y_n)\}$
• class of allowed function $\mathcal{F}$

use a predefined algorithm to compute $f\in \mathcal{F}$ with the goal:

$$y\approx f(x)$$

simplification using feature vector

convert input into a 1d vector, making machine learning generally applicable

• feature vector $\vec{x}\in X\subseteq {\mathbb{R}}^d$
• $\varphi :A\to X$
• training set $T_a=\{({\vec{x}}_1,y_1),\cdots ,({\vec{x}}_n,y_n)\}\subset {\mathbb{R}}^d\times {\mathbb{R}}^e$
• hypothesis space $\mathcal{H}$
• $Y\subseteq {\mathbb{R}}^e$

predefined algorithm produce $h\in \mathcal{H}$ so that

$$f(a)=h(\varphi (a))$$

loss

estimation of the error of $h$

$$\begin{gathered} \ell :Y\times Y\to {\mathbb{R}}^{+} \\ \ell (y_n,h({\vec{x}}_n)) \end{gathered}$$

zero-one loss

$$\ell (y,\hat{y}):=\{\begin{array}{ll}0& y=\hat{y}\\ 1& \text{otherwise}\end{array}$$

quadratic loss

$$\ell (y,\hat{y}):=(y-\hat{y}{)}^2$$

empirical risk

average lost based on the training set

$$L_T(h):=\frac{1}{N}\sum _{n=1}^N\ell (y_n,h({\vec{x}}_n))$$

three types of machine learning problems

classification problem

label given data

• classifier (predictor) $h$: the produced function

all possible training set

$$\mathcal{T}:=2^{X\times Y}$$

signature of machine learning function $\lambda$

$$\lambda :\mathcal{T}\to \mathcal{H}\text{such that}\lambda (T)=h$$

• $\lambda$ learn (or train) classifier $h$ from training set $T$
• inference: apply classifier $h$ on any data
  • testing: apply classifier $h$ on unseen data

classifier $h$ define a partition of $X$

regression problem

given data, return a vector

clustering problem

group given data

supervised/ unsupervised machine learning

supervised learning: classification, regression

unsupervised learning: clustering

polynomial data fitting

not machine learning but similar

$$\begin{gathered} A\vec{c}=\vec{b} \\ A=\left[\begin{array}{cccc}1& x_1& \cdots & x_1^k\\ ⋮& ⋮& & ⋮\\ 1& x_N& \cdots & x_N^k\end{array}\right] \\ \vec{b}=\left[\begin{array}{c}{y}_1\\ ⋮\\ y_N\end{array}\right] \\ \hat{\vec{c}}\in \underset{\vec{c}}{\mathrm{argmin}}\Vert A\vec{c}=\vec{b}{\Vert }^2 \end{gathered}$$

• number of monomial $m(d,k)=\left(\genfrac{}{}{0ex}{}{d+k}{k}\right)$

interpolation in polynomial data fitting

achieve $0$ loss

• $k=N-1\Rightarrow$ always interpolate
• overfitting

k-nearest neighbors predictor

remember the whole training set

$$T=\{({\vec{x}}_i,y_i)|i=1,\cdots ,N\}$$

return average of $y_n$s corresponding to the $k$ closest ${\vec{x}}_n$s to $\vec{x}$

• useful for both classification and regression
• smaller $k$ results in worse overfitting
• good interpolation and poor extrapolation

Voronoi diagram

gradient descent

stochastic gradient descent (SGD)

group training set randomly into mini-batch, use gradient from each mini-batch to descent

• mini-step are in the right direction on average
• epoch: using all data once

step size

• fixed

• decreasing

• momentum

  $${\vec{v}}_{k+1}={\mu }_k{\vec{v}}_k-{\alpha }_k\nabla f({\vec{z}}_k)$$

• line search

subgradient

logistic-regression classifier

• score-based

score function for linear boundary

$$s(\vec{x})=\sigma (a(\vec{x}))=\sigma (c+{\vec{u}}^T\vec{x})$$

signed distance to hyperplane

hyperplane $\chi \in {\mathbb{R}}^d$

$$b+{\vec{w}}^T\vec{x}=0\vec{w}\ne \vec{0}$$

• $\vec{w}$ is perpendicular to $\chi$

• distance of $\chi$ from origin

  $$\beta :=\frac{|b|}{\Vert \vec{w}\Vert }$$

• signed distance of $\vec{x}$ from $\chi$

  $$\Delta (\vec{x}):=\frac{b+{\vec{w}}^T\vec{x}}{\Vert \vec{w}\Vert }$$

logistic function

$$f(\Delta ):=\frac{1}{1+e^{-\Delta }}$$

then the score function is

$$s(\vec{x}):=f(a(\vec{x}))=f(b+{\vec{w}}^T\vec{x})=\frac{1}{1+e^{-b-{\vec{w}}^T\vec{x}}}$$

• activation $a(\vec{x})$ is signed distance scaled

softmax function

softmax function in activation $\vec{a}$

$$\begin{gathered} \vec{s}(\vec{x})=\left[\begin{array}{c}{s}_1(\vec{a})\\ ⋮\\ s_K(\vec{a})\end{array}\right] \\ \vec{a}(\vec{x})=\left[\begin{array}{c}{a}_1(\vec{x})\\ ⋮\\ a_K(\vec{x})\end{array}\right] \\ {s}_k(\vec{x})=f(a_k(\vec{x}))=\frac{e^{a_k}(\vec{x})}{{\sum }_{j=1}^K{e}^{a_j}(\vec{x})} \end{gathered}$$

cross entropy loss for binary classification

cross entropy loss of assigning score $p$ to point whose true label is $y$

$$\begin{gathered} \ell (y,p):=\{\begin{array}{ll}-\log p& y=1\\ -\log (1-p)& y=0\end{array} \\ =-y\log p-(1-y)\log (1-p) \end{gathered}$$

• differentiable so we can do gradient descent
• base of $\log$ does not matter
• resulting risk function is weakly convex

cross entropy loss for $K$-class case

$$\ell (y,\vec{p})=-\log p_y=-\sum _{k=1}^K{q}_k\log p_k$$

• true label $y$
• prediction $\vec{p}$
• one hot encoding $\vec{q}$ of $y$

support vector machine (SVM)

binary support vector machine

separating hyperplane for binary support vector machine

$$\begin{gathered} {\vec{n}}^T\vec{x}+c=0 \\ \vec{n}\in {\mathbb{R}}^d,\Vert \vec{n}\Vert =1,c\in \mathbb{R} \end{gathered}$$

• decision rule

  $$\begin{gathered} h(\vec{x})=\text{sign}({\vec{n}}^T\vec{x}+c) \\ \Rightarrow y({\vec{n}}^T\vec{x}+c)\ge 0 \end{gathered}$$

• margin for $(\vec{x},y)$ with parameter $\vec{v}=(\vec{n},c)$

  $${\mu }_{\vec{v}}(\vec{x},y):=y({\vec{n}}^T\vec{x}+c)$$

  • margin ${\mu }_{\vec{v}}(T)$ of training set

    $${\mu }_{\vec{v}}(T):=\underset{(\vec{x},y)\in T}{\min }{\mu }_{\vec{v}}(\vec{x},y)$$

  • linearly separable if ${\mu }_{\vec{v}}(T)>0$

hinge loss

reference margin ${\mu }^{\ast }>0$

$$\begin{gathered} {\ell }_{\vec{v}}(\vec{x},y):=\frac{1}{\mu \ast }\max \{0,{\mu }^{\ast }-{\mu }_{\vec{v}}(\vec{x},y)\} \\ =\max \{0,1-y({\vec{w}}^T\vec{x}+b)\} \end{gathered}$$

where

$$\vec{w}:=\frac{\vec{n}}{{\mu }^{\ast }},b=\frac{c}{{\mu }^{\ast }}$$

• separating hyperplane ${\vec{w}}^T\vec{x}+b=0$

empirical risk of binary support vector machine

$$L_T(\vec{w},b):=\frac{1}{2}\Vert \vec{w}{\Vert }^2+\frac{C_0}{N}\sum _{n=1}^N{\ell }_{(\vec{w},b)}({\vec{x}}_n,y_n)$$

• bigger $C_0\Rightarrow$ smaller ${\mu }^{\ast }$

soft linear support vector machine

$$({\vec{w}}^{\ast },b^{\ast })={\text{ERM}}_T(\vec{w},b)$$

subgradient of hinge function

$$\begin{gathered} \rho (z)=\max \{0,z\} \\ {\rho }^{\prime }(z)=\{\begin{array}{ll}1& z>0\\ 0& \text{otherwise}\end{array} \end{gathered}$$

support vector machine with kernel

representer theorem

$\forall$ loss function in the form

$$L^T(\vec{w},b)=R(\Vert \vec{w}\Vert )+S({\vec{w}}^T{\vec{x}}_1+b,\cdots ,{\vec{w}}^T{\vec{x}}_N+b)$$

where $R:{\mathbb{R}}_{+}\to \mathbb{R}$ increasing, $S:{\mathbb{R}}^N\to \mathbb{R}$,

$\exists {\beta }_1,\cdots {\beta }_N$ s.t.

$${\vec{w}}^{\ast }=\sum _{n=1}^N{\beta }_n{\vec{x}}_n$$

• proof: by writing

  $${\vec{w}}^{\ast }=\sum _{n=1}^N{\beta }_n{\vec{x}}_n+\vec{u}\text{for some}\vec{u}\in \text{span}\{{\vec{x}}_i\}$$

  and proving $\vec{u}=\vec{0}$ by contradiction

support vector

sample that are misclassified or classified correctly with a margin not larger than ${\mu }^{\ast }$

only support vector contribute to ${\vec{w}}^{\ast },b^{\ast }$

$$\begin{gathered} h(\vec{x})=\text{sign}\left(\sum _{n=1}^N{\beta }_n{\vec{x}}_n^T\vec{x}+b^{\ast }\right) \\ {L}^T(\vec{w},b)=\frac{1}{2}\sum _{n=1}^N{\beta }_m{\beta }_n{\vec{x}}_n^T{\vec{x}}_n+\frac{C_0}{N}\sum _{n=1}^N\rho \left(1-y_n\left(\sum _{n=1}^N{\beta }_m{\vec{x}}_n^T{\vec{x}}_n+b\right)\right) \end{gathered}$$

kernel for support vector machine

$$\begin{gathered} h(\vec{x})=\text{sign}\left(\sum _{n=1}^N{\beta }_{n}K({\vec{x}}_n,\vec{x})+b^{\ast }\right) \\ {L}^T(\vec{w},b)=\frac{1}{2}\sum _{n=1}^N{\beta }_m{\beta }_{n}K({\vec{x}}_n,{\vec{x}}_n)+\frac{C_0}{N}\sum _{n=1}^N\rho \left(1-y_n\left(\sum _{n=1}^N{\beta }_{m}K({\vec{x}}_n,{\vec{x}}_n)+b\right)\right) \end{gathered}$$

where kernel $K$

$$K(\vec{x},\vec{\xi }):=\vec{\phi }(\vec{x})\vec{\phi }(\vec{\xi })$$

for some $\vec{\phi }$

• $K(\vec{x},\vec{\xi })=K(\vec{\xi },\vec{x})$
• $K^2(\vec{x},\vec{\xi })\le K(\vec{x},\vec{x})K(\vec{\xi },\vec{\xi })$

$K$ is a kernel of $\{{\vec{x}}_i\}$

• $\iff C\ge 0$ where $C_{ij}=K({\vec{x}}_i,{\vec{x}}_j)$

• $\iff$ Mercer's condition: $\forall f:{\mathbb{R}}^d\to \mathbb{R}$ s.t.

  $${\int }_{{\mathbb{R}}^d}f(\vec{x})d\vec{x}$$

  is finite,

  $${\int }_{{\mathbb{R}}^d\times {\mathbb{R}}^d}K(\vec{x},\vec{\xi })f(\vec{x})f(\vec{\xi })d\vec{x}d\vec{\xi }\ge 0$$

• Gaussian kernel

  $$K(\vec{x},\vec{\xi })=e^{-\frac{\Vert \vec{x}-\vec{\xi }{\Vert }^2}{{\sigma }^2}}$$

  • radial basis function (RBF) SVM

• Data Science

Data Science

• Visualization
• data type
  • item
  • attribute
    • attribute type
  • link
  • position
  • grid
  • structured data
  • unstructured data
• symbolic display
  • graph
  • mark
  • channel
    • characteristic of channel
• analysis framework
  • user task
• graph theory
  • centrality
    • degree of vertex
    • betweeness of vertex
    • closeness of vertex
      • geodesic distance between vertex
    • eigenvector of vertex
    • clustering coefficient

Visualization

data type

item

discrete entry

attribute

measured property

attribute type

• nominal (categorical)

  with equality relationship

• ordinal

  with order

• quantitative (numerical)

  with algebra

  • ratio: with meaningful $0$
  • interval

link

relationship between item

position

spatial location

grid

sampling strategy for continuous data

structured data

• table: item & attribute
  • flat
  • multi-dimensional
• network: item & attribute & link
• field: grid & attribute
• geometry: position

unstructured data

text, audio, graphics…

symbolic display

• parallel coordinate
• treemap
• field
• choropleth map
• star plot

graph

• framework
  • scale
• content
  • mark
• label
  • title
  • axis

mark

represent item, link

• point
• line
• area

channel

represent attribute

• position
• color
  • hue
  • saturation
  • luminance
• shape
  • glyph
• tilt
• size
• area
• texture

characteristic of channel

• selective
• associative
• quantitative
• order
• length

analysis framework

four level

• domain situation
• data/task abstraction
• visual encoding/interaction idiom
• algorithm

three question

• what
• why
• how

user task

• query
  • retrieve value
  • find extremum
  • determine range
• search
  • sort
  • filter
• consume
  • compute derived value
  • characterize distribution
  • find anomaly
  • cluster
  • correlate

graph theory

$G(V,E)$

• independent set: no edge
• clique: all possible edge
• path: all edge can be consecutively traversed
• tree: no cycle
• network
• unconnected graph
• biconnected graph: no articulation point
  • articulation point: break the graph if deleted
• bipartite graph: edge between only vertex for two set

centrality

quantity to measure vertex importance

degree of vertex

number of connected node

• in-degree/ out degree for directed graph

betweeness of vertex

sum of number of shortest path through the vertex divided by number of shortest path between each pair of vertex

$$B(i)=\sum _{a,b}\frac{g_{aib}}{g_{ab}}$$

closeness of vertex

sum of geodesic distance between the vertex and every other

$$C(i)=\sum _{j}d(i,j)$$

geodesic distance between vertex

number of edge between them on the shortest path

eigenvector of vertex

adjacency matrix dot vector of degree

clustering coefficient

• Documentation

Documentation

• Pandoc

Pandoc

How to use Pandoc to produce a research paper

create paper.pdf from paper.md and paper.bib

pandoc --citeproc --bibliography=paper.bib --variable classoption=twocolumn --variable papersize=a4paper -s paper.md -o paper.pdf

• macOS

macOS

• Sucklessfy
  • DS.Store

Sucklessfy

allow apps from anywhere

sudo spctl --master-disable

DS.Store

remove all .DS_Store in subfolder

find . -name '.DS_Store' -type f -delete

• Mathematics

Mathematics

• Abstract Algebra
• integer
  • natural number
  • well-ordering axiom
  • division algorithm
    • divisibility
    • greatest common divisor
      • Euclidean algorithm
      • Bézout's identity
      • relatively prime
    • prime number
      • Euclid's lemma
      • fundamental theorem of arithmetic
• relation
  • partition of set
  • equivalence relation
    • equivalence class
  • modular arithmetic
    • congruence module $n$
    • congruence class
    • addition and multiplication in modular arithmetic
      • unit
      • zero divisor
• group
  • abelian group (commutative group)
  • nonabelian group
    • general linear group of degree $n$ over $R$
      • special linear group of degree $n$ over $R$
  • binary operation
    • associative binary operation
    • commutative binary operation
  • order of group
    • order of element in group
  • Torsion group
  • dihedral group $D_{2n}$
    • permutation of set
  • symmetric group on set
    • array notation of permutation
    • cycle notation of permutation
      • transposition
      • disjoint cycle
  • subgroup
    • subgroup test
    • centralizer of group
      • center of group
    • normalizer of group
  • cyclic group
    • fundamental theorem of cyclic group
  • homomorphism
    • well-defined map
    • automorphism
    • isomorphism
      • equivalence relation from isomorphism
      • cyclic isomorphism
      • Cayley's theorem
    • kernel and image of homomorphism
  • coset
    • set of coset
      • index of subgroup in group
      • Lagrange's theorem
  • normal subgroup
    • normal subgroup test
  • quotient subgroup
    • natural projection
  • isomorphism theorem
    • first isomorphism theorem
    • second isomorphism theorem (diamond theorem)
    • third isomorphism theorem
    • forth isomorphism theorem
• ring
  • commutative ring
  • ring with identity
  • division ring
  • field
  • zero divisor of ring
    • integral domain
  • unit of ring
  • subring
    • subring test
    • center of ring
    • characteristic of ring
    • nilpotent of commutative ring with identity
  • polynomial ring
    • polynomial in $x$ with coefficient in $R$
  • matrix ring
    • scalar matrix
  • ring homomorphism
  • ideal of ring
    • ideal test
    • maximal ideal
    • prime ideal
  • quotient ring
  • isomorphism theorem for ring
    • first isomorphism theorem for ring
    • second isomorphism theorem for ring
    • third isomorphism theorem for ring
    • forth isomorphism theorem for ring

Abstract Algebra

integer

$$\mathbb{Z}:=\{\cdots ,-2,-1,0,-1,-2,\cdots \}$$

natural number

$$\mathbb{N}:=\{0,1,2,\cdots \}$$

well-ordering axiom

$\forall R\subseteq \mathbb{N},R\ne \varnothing ,\exists a\in R$ s.t. $\min (R)=a$

division algorithm

$\forall a,b\in \mathbb{Z},b>0,\exists !q,r\in \mathbb{Z}$, s.t.

$$a=bq+r,0\le r<b$$

divisibility

$b|a$, or $b$ divide $a\iff \exists c\in \mathbb{Z}$, s.t. $a=bc$

• $b\nmid a$, or $b$ do not divide $a$
• $b|a\iff b|(-a)$
• $a\ne 0,b|a\Rightarrow b\le |a|$

greatest common divisor

$a,b\in \mathbb{Z}\setminus \{0\},\exists !d:=\gcd (a,b)$, s.t.

1. $d|a,d|b$
2. $c|a,c|b\Rightarrow c\le d$

or

1. $d|a,d|b$
2. $c|a,c|b\Rightarrow c|d$

Euclidean algorithm

$a,b\in \mathbb{Z}\setminus \{0\}$

1. let $r_{-2}=a,r_{-1}=b$

2. apply division algorithm on $r_{i-1},r_i$ until $r_{n+1}=0$

   $$r_{i-1}=q_{i+1}{r}_i+r_{i+1}$$

3. $r_n=\gcd (a,b)$

• $a,b,q,r\in \mathbb{Z},b>0,a=bq+r\Rightarrow \gcd (a,b)=\gcd (b,r)$

Bézout's identity

$a,b\in \mathbb{Z}\setminus \{0\},\exists u,v$ s.t.

$$\gcd (a,b)=au+bv$$

• $\gcd (a,b)=\min (\{ax+by|x,y\in \mathbb{Z}\})$
• $x,y\in \mathbb{Z},c=ax+by\Rightarrow \gcd (a,b)|c$
• find $u,v$: substitute $\gcd (a,b)$ from the last equation in Euclidean algorithm up

relatively prime

$a,b$ are relatively prime $\iff \gcd (a,b)=1$

• $\gcd (a,b)=1\iff \exists x,y\in \mathbb{Z},ax+by=1$
• $a|bc,\gcd (a,b)=1\Rightarrow a|c$

prime number

$p\in \mathbb{Z}$, then $p$ is prime $\iff p\ne 0,p\ne \pm 1$, the only divisor of $p$ are $\pm 1,\pm p$

• composite number: not prime

Euclid's lemma

$p$ prime, $p|ab\Rightarrow p|a$ or $p|b$

• $p\in \mathbb{Z}\setminus \{0,\pm 1\}$, then $p$ prime $\iff$ if $p|ab$, then $p|a$ or $p|b$
• $p$ prime, $p|a_1{a}_2\cdots a_n\Rightarrow \exists i,p|a_i$

fundamental theorem of arithmetic

$\forall n\in \mathbb{Z}\setminus \{0,\pm 1\},n$ can be factored uniquely into product of primes

relation

relation $R$ on $A$ is a subset $R\subseteq A\times A$

$aRb$ or $a$ is related to $b\iff (a,b)\in R$

• $a/Rb$ or $a$ is not related to $b$

partition of set

$A$ is a non-empty set, partition of $A$

$$\mathcal{P}:\{A_i|i=1,2,\cdots \}$$

s.t.

1. $\forall i\ne j,A_i\cap A_j=\varnothing$
2. $A=\bigcup _i{A}_i$

• $R_{\mathcal{P}}:=\{(a,b)|\exists A_i,a\in A_i,b\in A_i\}$ is equivalence relation

equivalence relation

1. reflexive: $aRa$
2. symmetric: $aRb\Rightarrow bRa$
3. transitive: $aRb,bRc\Rightarrow aRc$

equivalence class

equivalence class of representative $a$

$$[a]:=\{x\in A|xRa\}$$

• $aRb\iff [a]=[b]$

• $[a],[b]$ are either disjoint or identical

• quotient set of $A$ by $R$

  $$A/R:=\{[a]|a\in A\}$$

  is partition of $R$

modular arithmetic

$a,b,n\in \mathbb{Z},n>0$, then

$a{\equiv }_{n}b$ or $a\equiv b$ (mod $n$) or $a$ is congruent to $b$ modulo $n\iff n|(a-b)$

congruence module $n$

$\mathbb{Z}/n$ ($\mathbb{Z}$ mod $n$) or quotient set of $\mathbb{Z}$ by ${\equiv }_n$

• $\mathbb{Z}/n$ is equivalence relation on $\mathbb{Z}$

congruence class

equivalence class of $a$ modulo $n$

$$\begin{gathered} [a{]}_n:=\{x\in \mathbb{Z}|x{\equiv }_{n}a\} \\ =\{a+nk|k\in \mathbb{Z}\} \end{gathered}$$

• there are $n$ distinct congruence classes

addition and multiplication in modular arithmetic

$$\begin{gathered} [a]+[b]=[a+b] \\ [a][b]=[ab] \end{gathered}$$

• addition and multiplication are well-defined
• $\forall [a]\in \mathbb{Z}/n,\exists !$ additive inverse
• $[a]\ne [0]$ either has unique multiplicative inverse or it has not

unit

$\exists x\in \mathbb{Z}/n,[a]x=[1]$

• $[a]$ is unit $\iff \gcd (a,n)=1$

zero divisor

$\exists x\ne [0],[a]x=[0]$

• $p\in \mathbb{N}\setminus \{0,1\}$, then

  $p$ is prime

  $\iff \forall [a]\ne [0]$, $[a]$ is unit

  $\iff [b][c]=[0]\Rightarrow [b]=[0]$ or $[c]=[0]$, or no zero divisor

group

ordered pair $(G,\ast )$

• set $G$
• binary operation $\ast$

axiom group satisfy:

1. $\ast$ is associative
2. identity: $\exists e\in G,\forall a\in G,a\ast e=e\ast a=a$
3. inverse: $\forall a\in G,\exists a^{-1}\in G,a\ast a^{-1}=a^{-1}\ast a=e$

property

1. $e$ is unique
2. $\forall a\in G$, $a$ has unique inverse
3. $a\ast x=b$ and $y\ast a=b$ has unique solution, cancellation law work

• $(a^{-1}{)}^{-1}=a$
• $(a\ast b{)}^{-1}=b^{-1}\ast a^{-1}$
• value of $a_1\ast a_2\ast \cdots \ast a_n$ is independent of the bracketing

abelian group (commutative group)

$\ast$ is commutative

• $\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{C},\mathbb{Z}/n,{\mathbb{R}}^{m\times n}$ under $+$
• $\mathbb{Q}\setminus \{0\},\mathbb{R}\setminus \{0\},\mathbb{C}\setminus \{0\},(\mathbb{Z}/n{)}^{\times }$ under $\cdot$

nonabelian group

• dihedral group of order $2n$, $D_{2n}$
• $(GL(n,\mathbb{R}),\cdot )$

general linear group of degree $n$ over $R$

$$GL(n,R):=\{A\in R^{n\times n}|A\text{ is invertible}\}$$

special linear group of degree $n$ over $R$

$$SL(n,R):=\{A\in GL(n,R)|\det A=1\}$$

binary operation

$$\ast :G\times G\to G$$

associative binary operation

$$(a\ast b)\ast c=a\ast (b\ast c)$$

commutative binary operation

$$a\ast b=b\ast a$$

order of group

$|G|$, or order of $G$, is the number of distinct elements in $G$

order of element in group

$|a|$, or order of $a$, is the smallest $n\in {\mathbb{Z}}_{+}$ s.t.

$$a^n=e$$

or $\infty$ if $n$ DNE

• $e,a,a^2,\cdots ,a^{n-1}$ are distinct
• $a^m=1\iff n|m$
• $\forall m\in {\mathbb{Z}}_{+},|a^m|=\frac{n}{\gcd (m,n)}$

Torsion group

$G$ is a Torsion group, then $\forall a\in G,|a|$ is finite

• Torsion-free group: $\forall a\in G,a\ne e,|a|=\infty$

• Torsion subgroup of $G$: for abelian group $G$,

  $$\text{Tor}(G):=\{a\in G||a|\text{ is finite}\}$$

• $ab=ba,\gcd (|a|,|b|)=1\Rightarrow |ab|=|a||b|$

• $G$ is abelian Torsion group, then $c$ has largest order $\Rightarrow \forall a\in G,|a|||c|$

dihedral group $D_{2n}$

rotation ($r$) and reflection ($s$) of n-gon

$$\begin{gathered} \{1,s,r,sr,r^2,s{r}^2,\cdots ,r^{n-1},s{r}^{n-1}\}n\ge 3 \\ (r^i)(k)=i+k\mathrm{mod}n \end{gathered}$$

• order $2n$
• degree $n$
• $|s|=2$
• $|r|=n$
• $\forall 0\le i\ne j\le n-1,s{r}^i\ne s{r}^j$
• $\forall 0\le i\le n,r^{i}s=s{r}^{-i}$

permutation of set

permutation of $X$: bijection

$$\sigma :X\to X$$

symmetric group on set

set $\Omega \ne \varnothing$

$S_{\Omega }$, the set of permutation of $\Omega$

$(S_{\Omega },\circ )$, symmetric group on $\Omega$

• $n\ge 1,\Omega =X_n\Rightarrow (S_n,\circ )$, symmetric group of degree $n$
• $|S_{\Omega }|=n!$
• $n\ge 3\Rightarrow (S_n,\circ )$ nonabelian

array notation of permutation

$\alpha$ is permutation on $X_n$

$$\alpha =\left(\begin{array}{cccc}1& 2& \cdots & n\\ \alpha (1)& \alpha (2)& \cdots & \alpha (n)\end{array}\right)$$

cycle notation of permutation

cyclically permute and fix the rest

$$(a_1{a}_2\cdots a_m)=\left(\begin{array}{cccc}{a}_1& a_2& \cdots & a_m\\ a_2& a_3& \cdots & a_1\end{array}\right)$$

• $m$-cycle (or cycle of length $m$)

transposition

$2$-cycle

• $\forall \sigma \in S_n,\sigma$ can be expressed as product of transposition
  • not unique
  • even permutation: length of such transposition is even
  • odd permutation

disjoint cycle

no common number

• $\alpha ,\beta \in S_n$ disjoint $\Rightarrow \alpha \beta =\beta \alpha$
• $\forall \pi \in S_n,\pi \ne 1,\pi$ can be uniquely expressed as product of disjoint cycle of length at least 2

subgroup

$H\le G$, or $H\subseteq G$ is a subgroup of $G$

1. $H\ne \varnothing$
2. $\forall x,y\in H,xy\in H$
3. $\forall x\in H,x^{-1}\in H$

• $H<G$, or $H$ is a proper subgroup of $G$

subgroup test

1. $H\le G\iff$
   1. $H\ne \varnothing$
   2. $\forall x,y\in H,x{y}^{-1}\in H$
2. $|G|<\infty ,H\le G\iff$
   1. $H\ne \varnothing$
   2. $\forall x,y\in H,xy\in H$

centralizer of group

$$C_G(A):=\{g\in G|\forall a\in A,ga=ag\}$$

• $C_G(a)$ if $A=\{a\}$

center of group

$$Z(G):=\{g\in G|\forall a\in G,ga=ag\}$$

normalizer of group

$$N_G(A):=\{g\in G|gA{g}^{-1}=A\}$$

where

$$gA{g}^{-1}:=\{ga{g}^{-1}|a\in A\}$$

for group $G$ and subset $A\subseteq G$

• $C_G(A)\le N_G(A)\le G$
• $G$ abelian $\Rightarrow Z(G)=G,C_G(A)=N_G(A)$

cyclic group

$$G=⟨x⟩=\{x^n|n\in \mathbb{Z}\}$$

• generator $x$
• cyclic group are abelian
• $|G|=|x|$

fundamental theorem of cyclic group

1. $H\le G\Rightarrow \exists !k\in \mathbb{N},k={\min }_k\{x^k\in H\},H=⟨x^k⟩$
2. $|G|=n\Rightarrow$
   • $\forall a\in \mathbb{N},a|n,\exists !A,|A|=a$
     • $A=⟨x^d⟩$
     • $d=\frac{n}{a}$
   • $\forall m\in \mathbb{Z},⟨x^m⟩=⟨x^{\gcd (m,n)}⟩$
   • $\forall i,j,x^i=x^j\iff i\equiv j\mathrm{mod}n$
3. $|G|=\infty \Rightarrow \forall m\in \mathbb{Z},⟨x^m⟩=⟨x^{|m|}⟩$

homomorphism

$(G,\cdot ),(H,\cdot )$ are group

well-defined map $\phi :G\to H$ is homomorphism $\iff$

$$\forall a,b\in G,\phi (ab)=\phi (a)\phi (b)$$

property

1. $\phi (1_G)=1_H$
2. $\forall n\in \mathbb{Z},\phi (a^n)=\phi (a{)}^n$

• monomorphism: $\phi$ injective
• epimorphism: $\phi$ surjective
• $\cong$, or isomorphism: $\phi$ bijective

well-defined map

$f:A\to B$ is well-defined $\iff$

$$\forall x=y\in A\Rightarrow f(x)=f(y)$$

automorphism

isomorphism from $G$ to $G$

• inner automorphism of $G$, ${\phi }_a(g)=ag{a}^{-1}(a\in G)$

isomorphism

property

1. $|G|=|H|$
2. $G$ abelian $\iff H$ abelian
3. $\forall g\in G,|g|=|\phi (g)|$
4. $\forall n\in {\mathbb{Z}}^{+},G,H$ have same number of elements of order $n$

• $|G|=p$ prime $\Rightarrow G\cong \mathbb{Z}/p$

equivalence relation from isomorphism

$\mathcal{G}$ is set of groups

$\cong$ is equivalence relation on $\mathcal{G}$

cyclic isomorphism

$G=⟨x⟩$

• $|x|=\infty \Rightarrow G\cong \mathbb{Z}$
• $|x|=n\Rightarrow G\cong \mathbb{Z}/n$

Cayley's theorem

$\forall$ group $G$, $\exists$ permutation $H\le S_G$, s.t. $G\cong H$

kernel and image of homomorphism

$\phi :G\to H$ is homomorphism

$h\in H$

1. kernel of $\phi$

   $$\text{Ker }\phi :=\{a\in G|\phi (a)=1\}$$

   • $\text{Ker }\phi \le G$
   • measure how much $\phi$ is not injective
   • $\phi$ is injective $\iff \text{Ker }\phi =\{1\}$

2. image of $\phi$

   $$\text{Im }\phi =\phi (G):=\{\phi (a)|a\in G\}$$

   • $\text{Im }\phi \le H$
   • $\phi$ is injective $\iff \text{Im }\phi \cong G$

3. fiber of $h$ under $\phi$

   $${\phi }^{-1}(h):=\{a\in G|\phi (a)=h\}$$

   • $\phi$ is surjective $\iff \text{Im }\phi =H$

coset

$H\le (G,\cdot )$, $g,a,b\in G$

1. left coset of $H$ in $G$

   $$gH:=\{gh|h\in H\}$$

   • $\exists$ bijection between $H$ and $gH$
   • $aH=bH\iff b^{-1}a\in H$
   • $aH=bH$ or $aH\cap bH=\varnothing$

2. right coset of $H$ in $G$

   $$Hg:=\{hg|h\in H\}$$

   • $\exists$ bijection between $H$ and $Hg$
   • $Ha=Hb\iff a{b}^{-1}\in H$
   • $Ha=Hb$ or $Ha\cap Hb=\varnothing$

3. $g$ is representative

• left and right coset are not necessarily equal
• $gH\le H\iff g=1$
• $|H|=|gH|=|Hg|$

set of coset

1. set of left coset

   $$G/H:=\{aH|a\in G\}$$

2. set of right coset

   $$H\setminus G:=\{Ha|a\in G\}$$

• $\exists$ bijection between $G/H$ and $H\setminus G$

index of subgroup in group

index of $H$ in $G$

$$[G:H]$$

is number of distinct left (right) coset

Lagrange's theorem

1. $|H|||G|$
2. $[G:H]=\frac{|G|}{|H|}$

for finite $G$

• $a\in G\Rightarrow |a|||G|$
• $\forall a\in G,a^{|G|}=1$

normal subgroup

$N⊴G$, or $N$ is normal in $G\iff$

$$\forall a\in G,aN=Na$$

normal subgroup test

1. $N⊴G$
2. $\iff \forall a\in G,aN{a}^{-1}\subseteq N$
3. $\iff \forall a\in G,aN{a}^{-1}=N$
4. $\iff N_G(N)=G$
5. $\iff$ if $aN=bN,cN=dN$, then $(ac)N=(bd)N$

quotient subgroup

$N⊴G$

$G/N=N\setminus G$ is the quotient group of $G$ by $N$

under operation $\cdot$:

$$(aN)(bN):=(ab)N$$

• $|G/N|=[G:N]$

natural projection

$N⊴G$

natural projection of $G$ onto $N$

homomorphism $\pi :G\to G/N$

$$\pi (a)=aN$$

• $\pi$ is epimorphism
• $\text{Ker }\pi =N$

isomorphism theorem

first isomorphism theorem

$\phi :G\to H$ homomorphism $\Rightarrow$

$$G/\text{Ker }\phi \cong \text{Im }\phi$$

• under $\Phi :G/\text{Ker }\phi \to \text{Im }\phi$

  $$\Phi (g\text{Ker }\phi ):=\phi (g)$$

second isomorphism theorem (diamond theorem)

$K\le G,N\le G,N⊴G\Rightarrow$

1. $KN\le G$
2. $K\cap N⊴K$
3. $N⊴KN$
4. $K/K\cap N\cong KN/N$
5. $[KN:K]=[N:K\cap N]$

third isomorphism theorem

$H⊴G,K⊴G,K\le H$

1. $H/K⊴G/K$
2. $(G/K)/(H/K)\cong G/H$

   • $G/K\cong G/H$ under $\Gamma :G/K\to G/H$

     $$\Gamma (gK):=gH$$

forth isomorphism theorem

$N⊴G$, natural projection $\pi :G\to G/N$

$\exists$ bijection $\Pi$

$$\begin{gathered} \Pi :\{A\le G|N\subseteq A\}\to \{\mathcal{A}\le G/N\} \\ \Pi (A)=\pi (A)=\{\pi (a)|a\in A\}=A/N \end{gathered}$$